# """节点，保存数据和后继节点"""
class Node():
    def __init__(self, data, pointer):
        self.data = data
        self.pointer = pointer

# 输出链表
def outputNodes(linkedList):
    currentPointer = startPointer
    while currentPointer!=-1 :
        print(linkedList[currentPointer].data)
        currentPointer = linkedList[currentPointer].pointer
    print("-------------")

# 插入到开始位置
def insertStart(newItem):
    global startPointer
    global freePointer
    if freePointer == -1:
        return
    else:
        newNodePointer = freePointer
        linkedList[newNodePointer].data = newItem
        freePointer = linkedList[freePointer].pointer
        linkedList[newNodePointer].pointer = startPointer
        startPointer = newNodePointer


# 插入到最后位置
def insertEnd(newItem):
    global startPointer
    global freePointer
    if freePointer == -1:
        return
    else:
        newNodePointer = freePointer
        linkedList[newNodePointer].data = newItem
        linkedList[newNodePointer].pointer = -1
        freePointer = linkedList[freePointer].pointer
        thisNodePtr = startPointer
        previousPointer = -1
        while thisNodePtr != -1 :
            previousPointer = thisNodePtr
            thisNodePtr = linkedList[thisNodePtr].pointer
        linkedList[previousPointer].pointer = newNodePointer
# 按顺序插入新元素
def insertOrder(newItem):
    global startPointer
    global freePointer
    if freePointer < 0 or freePointer > len(linkedList)-1:
        return
    else:
        newNodePointer = freePointer
        linkedList[newNodePointer].data = newItem
        freePointer = linkedList[freePointer].pointer
        thisNodePtr = startPointer
        previousPointer = -1
        while thisNodePtr != -1 and linkedList[thisNodePtr].data<newItem:
            previousPointer = thisNodePtr
            thisNodePtr = linkedList[thisNodePtr].pointer
        if previousPointer == -1:  #如果插入点在一开始
            linkedList[newNodePointer].pointer=startPointer
            startPointer=newNodePointer
        else:
            linkedList[newNodePointer].pointer  = thisNodePtr
            linkedList[previousPointer].pointer = newNodePointer


# 在指定的位置插入一个节点
def insertNode(newItem, insertCount):
    global startPointer
    global freePointer
    if freePointer ==-1 or insertCount<1 or insertCount>len(linkedList):
        return False
    else:
        newNodePointer = freePointer
        linkedList[newNodePointer].data = newItem
        freePointer = linkedList[freePointer].pointer
        # 头添加元素
        if insertCount == 1:
            linkedList[newNodePointer].pointer = startPointer
            startPointer = newNodePointer
        # 其它位置添加元素
        else:
            count = 2
            currentPointer = linkedList[startPointer].pointer
            prePointer = startPointer
            while count < insertCount and currentPointer!=-1:
                prePointer = currentPointer
                currentPointer = linkedList[currentPointer].pointer
                count+=1
            linkedList[newNodePointer].pointer = currentPointer
            linkedList[prePointer].pointer = newNodePointer
        return True


def findNode(dataItem):
    currentNodePtr = startPointer
    pos = False
    while currentNodePtr!=-1 and linkedList[currentNodePtr].data!=dataItem:
        currentNodePtr = linkedList[currentNodePtr].pointer
    if currentNodePtr!=-1:
        pos = True
    return pos

# 删除
def deleteNodeByData(dataItem):
    global startPointer
    global freePointer
    currentNodePtr = startPointer
    while currentNodePtr!=-1 and linkedList[currentNodePtr].data!=dataItem:
        previousPtr = currentNodePtr
        currentNodePtr = linkedList[currentNodePtr].pointer
    if currentNodePtr!=-1: #node exits in list
        if currentNodePtr==startPointer: #first node to be deleted
            startPointer = linkedList[startPointer].pointer
        else:   #it is not the start node
            linkedList[previousPtr].pointer = linkedList[currentNodePtr].pointer
        linkedList[currentNodePtr].data = None
        linkedList[currentNodePtr].pointer = freePointer
        freePointer = currentNodePtr




def deleteNode(linkedList,deleteCount):
    global startPointer
    global freePointer
    if freePointer!=-1:
        return False
    else:
        # 删除第一个节点
        if deleteCount == 1:
            # 保留下一个节点，再更新
            pointer = linkedList[startPointer].pointer
            linkedList[startPointer].pointer = emptyPointer
            emptyPointer = startPointer
            startPointer = pointer
        # 删除其它元素
        else:
            currentPointer = linkedList[startPointer].pointer
            prePointer = startPointer
            count = 2
            while count<deleteCount:
                # 先保留当前指针，再往后挪
                prePointer = currentPointer
                currentPointer = linkedList[currentPointer].pointer
                count += 1
            linkedList[prePointer].pointer = linkedList[currentPointer].pointer
            linkedList[currentPointer].pointer = emptyPointer
            emptyPointer = currentPointer

if __name__ == '__main__':
    startPointer = 0
    freePointer = 2
    #              0                   1           2                 3             4            5
    linkedList = [Node("A", 4), Node("E", -1), Node(None, 3), Node(None, -1), Node("B", 5), Node("C", 1)]
    outputNodes(linkedList)
    # # insertStart("@")
    # # insertEnd("G")
    # # insertOrder("@")
    # insertNode("E",7)
    # deleteNodeByData("F")
    # outputNodes(linkedList)
    print(findNode("F"))

